漫画算法学习笔记

2024-03-28 22:26| 来源: 网络整理| 查看: 265

漫画算法概述数据结构基础数组和链表树排序面试中的算法如何判断链表有环如果链表有环，如何求出环的长度？如果链表有环，如何求出入环节点？最小栈的实现最大公约数如何判断一个数是否为2的整数次幂无序数组排序后的最大相邻差如何用栈实现队列寻找全排列的下一个数删去k个数字后的最小值如何实现大整数相加实际应用

近期看了本书《obook.cc-漫画算法：小灰的算法之旅±+魏梦舒》推荐买这本书很有意思，也学到很多。比写业务有趣多了。好记性不如烂笔头，所以记录下笔记，顺便用自己的方式c#实现以下，毕竟名言说的好Talk is cheap, show me the code。

基本流程是：先看题，有思路直接写代码，没思路接着看接替思路，然后自己写，没怎么看书里的代码。可能还有问题，比如没考虑全边界什么的。写完后不运行，根本不敢保证代码没问题，并且初次几乎都有问题，还要加强！！！代码只是检测，最重要的是解题思路，以及遇到类似问题该往哪个方向思考的思路！推荐看下这个：https://blog.csdn.net/qq_34115899/article/details/87718847

概述数据结构基础数组和链表

主要是线性结构的数组和链表，以及栈和队列。（略）

树排序

所有的排序我都总结了下，放另一篇了。《排序总览》

面试中的算法如何判断链表有环

两个指针，差速遍历

public class Node { public int data; public Node Next; } public static bool IsCycle(Node head) { Node node1 = head; Node node2 = head; while (node2 != null && node2.Next != null) { node1 = node1.Next; node2 = node2.Next.Next; if (node1 == node2) { return true; } } return false; } 如果链表有环，如何求出环的长度？

在判断到有环后，两个节点继续循环，直到再次相遇，两者差速是1，所以环长度是循环的次数乘以1：count * 1

public static int GetCycle(Node head) { Node node1 = head; Node node2 = head; while (node2 != null && node2.Next != null) { node1 = node1.Next; node2 = node2.Next.Next; if (node1 == node2) { break; } } node1 = node1.Next; node2 = node2.Next.Next; int count = 1; while (node1 != node2) { node1 = node1.Next; node2 = node2.Next.Next; count++; } return count; } 如果链表有环，如何求出入环节点？最小栈的实现

实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素（getMin）3个方法。要保证这3个方法的时间复杂度都是O(1)。

设原有的栈叫作栈A，此时创建一个额外的“备胎”栈B，用于辅助栈A。每次Push时，都和B中比较，小于就也Push到B中。

private Stack stackA = new Stack(); private Stack stackB = new Stack(); public void Push(int item) { stackA.Push(item); if (stackB.Count != 0 && stackB.Peek() int item = stackA.Pop(); if (item == stackB.Peek()) { stackB.Pop(); } } public int GetMinValue() { return stackB.Peek(); } 最大公约数

写一段代码，求出两个整数的最大公约数，要尽量优化算法的性能。

如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。

更相减损法:

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

static int cishu = 0; static int chashu = 0; private static int Zuidagongyueshu(int a, int b) { if (a > 0 && b > 0) { if (a == b) { return a; } if (a return b; } Chu2(a, b); Cha(a, b); return cishu != 0 ? cishu * chashu : chashu; } return -1; } private static void Chu2(int a, int b) { if (a % 2 != 0 || b % 2 != 0) { return; } a = a / 2; b = b / 2; cishu++; Chu2(a, b); } private static void Cha(int a, int b) { int chazhi = a - b; if (chazhi == b) { return; } if (chazhi a = chazhi; } Cha(a, b); } 如何判断一个数是否为2的整数次幂

实现一个方法，来判断一个正整数是否是2的整数次幂（如16是2的4次方，返回true；18不是2的整数次幂，则返回false）

public bool IsPowerOf2(int num) { return (num & num - 1) == 0; } 无序数组排序后的最大相邻差

有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低

如何用栈实现队列

用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队。

Stack s1 = new Stack(); Stack s2 = new Stack(); public void Push(int item) { s1.Push(item); } public int Pop() { DaoZhi(s1, s2); int value = s2.Pop(); DaoZhi(s2, s1); return value; } public void DaoZhi(Stack oldS, Stack newS) { newS.Clear(); int count = oldS.Count; for (int i = 0; i

【本文地址】

公司简介

联系我们